/*
 * @lc app=leetcode.cn id=437 lang=cpp
 * @lcpr version=30204
 *
 * [437] 路径总和 III
 */

// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution
{
public:
    // 方法一：相当于暴力搜索 O(N^2)
    //     int pathSum(TreeNode* root, int targetSum) {
    //         if (!root) return 0;

    //         // 计算以当前节点为起点的路径数量
    //         int count = DFS(root, targetSum);

    //         // 递归计算左右子树的路径数量
    //         count += pathSum(root->left, targetSum);
    //         count += pathSum(root->right, targetSum);

    //         return count;
    //     }
    // private:
    //     int DFS(TreeNode* node, long long targetSum)
    //     {
    //         if(!node) return 0;

    //         int count = 0;

    //         // 如果当前路径和等于 targetSum，计数器加 1
    //         if (node->val == targetSum) {
    //             count++;
    //         }

    //         // 递归计算左右子树的路径和
    //         count += DFS(node->left, targetSum - node->val);
    //         count += DFS(node->right, targetSum - node->val);

    //         return count;
    //     }
    unordered_map<long long, int> prefix;

    int dfs(TreeNode *root, long long curr, int targetSum)
    {
        if (!root)
        {
            return 0;
        }

        int ret = 0;
        curr += root->val;
        if (prefix.count(curr - targetSum))
        {
            ret = prefix[curr - targetSum];
        }

        prefix[curr]++;
        ret += dfs(root->left, curr, targetSum);
        ret += dfs(root->right, curr, targetSum);
        prefix[curr]--;

        return ret;
    }

    int pathSum(TreeNode *root, int targetSum)
    {
        prefix[0] = 1;
        return dfs(root, 0, targetSum);
    }
};
// @lc code=end

/*
// @lcpr case=start
// [10,5,-3,3,2,null,11,3,-2,null,1]\n8\n
// @lcpr case=end

// @lcpr case=start
// [5,4,8,11,null,13,4,7,2,null,null,5,1]\n22\n
// @lcpr case=end

 */
